package com.leetcode.array_matrix;

import java.util.*;

/**
 * @author Dennis Li
 * @date 2020/9/14 9:44
 */
public class CheckSubarraySum_523 {

    /*
    * A、两个不同的前缀和的余数相等，意味着这两个前缀和之差就是k的倍数
      B、sum=sum%k对求解前缀和的余数没有影响，他只是让sum和余数之间的差去掉，但为什么这样子做呢，有两个好处
        a.加入①,碰到[1,0,1] k=2这种nums[i]都小于k的，sum==k的，处理框架依然在A的范围内
        b.碰到k==0时，处理框架也依然在A的范围
    * */
    public boolean checkSubarraySum(int[] nums, int k) {
        int sum = 0;
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (k != 0) {
                // 两个不同的前缀和的余数相等，意味着这两个前缀和之差就是k的倍数
                sum = sum % k;
            }
            if (map.containsKey(sum)) {
                // 不是原来的点
                if (i - map.get(sum) > 1) {
                    return true;
                }
            } else
                map.put(sum, i); // 记录标号
        }
        return false;
    }


}
